package org.gushi.algorithm.a06;

/**
 * 著作权归https://pdai.tech所有。
 * 链接：https://www.pdai.tech/md/algorithm/alg-sort-x-shell.html
 * <p>
 * 希尔排序实质上是一种分组插入方法。它的基本思想是: 对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，
 * 所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，
 * 并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。
 */
public class ShellSort<E extends Comparable<E>> {

    private E[] list;


    public ShellSort(E[] list) {
        this.list = list;
    }


    public E[] sort() {

        int[] gaps = new int[]{4, 2, 1};

        for (int index = 0; index < gaps.length; index++) {
            int gap = gaps[index];
            for (int i = 0; i <= gap; i++) {
                int j = i;
                while (j < list.length) {
                    if ((gap + j) >= list.length) {
                        break;
                    }
                    if (list[j].compareTo(list[j + gap]) > 0) {
                        E temp = list[j + gap];
                        list[j + gap] = list[j];
                        list[j] = temp;
                    }
                    j = j + gap;
                }
            }
        }

        return list;
    }

}
